package 左哥算法.ch02二分;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class Ch02归并排序与快排 {
    /**
     * 归并排序
     * 思路：
     * 先将数组分为两部分，递归调用函数让这两部分有序
     * 对两部分的元素依次进行比较，小到大放入一个新的数组中，当一侧全部放入后，将另一侧剩下部分直接放入新的数组中
     */
    @Test
    public void test01() {
        int[] nums = {9, 3, 5, 1, 4, 7, 2, 6, 8, 0};
        fun1(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    public void fun1(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int m = l + r >> 1;
        fun1(arr, l, m);
        fun1(arr, m + 1, r);
        merge1(arr, l, m, r);
    }

    private void merge1(int[] arr, int l, int m, int r) {
        int i = 0;
        int p1 = l, p2 = m + 1;
        int[] nums = new int[r - l + 1];
        while (p1 <= m && p2 <= r) {   //只要有一侧放入
            nums[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        //当一侧放入心数组后，将另一侧的剩下部分也放入
        while (p2 <= r) {
            nums[i++] = arr[p2++];
        }
        while (p1 <= m) {
            nums[i++] = arr[p1++];
        }
        for (int j = l, k = 0; j <= r; j++) {
            arr[j] = nums[k++];
        }
    }

    /**
     * 小和问题
     */
    @Test
    public void test2() {
//        System.out.println(2+(4-2>>1));
        int[] nums = {1, 3, 4, 2, 5};
        System.out.println(fun2(nums, 0, nums.length - 1));
    }

    public int fun2(int[] nums, int l, int r) {
        if (l == r) {  //如果左侧没有了则返回0
            return 0;
        }
        int m = l + ((r - l) >> 1);
        return fun2(nums, l, m) +       //先让左侧求出最小和然后排好序
                fun2(nums, m + 1, r) +  //让右侧求出最小和并排序
                merge2(nums, l, m, r);   //算出右侧相对与左侧的最小和，并排序
    }

    public int merge2(int[] arr, int l, int m, int r) {
        int i = 0;
        int p1 = l, p2 = m + 1;
        int[] nums = new int[r - l + 1];
        int res = 0;
        while (p1 <= m && p2 <= r) {
            res += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0;
            nums[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p2 <= r) {
            nums[i++] = arr[p2++];
        }
        while (p1 <= m) {
            nums[i++] = arr[p1++];
        }
        for (int j = l, k = 0; j <= r; j++) {
            arr[j] = nums[k++];
        }
        return res;
    }

    /**
     * 快速排序
     * 选定数组中一个数，将比他大的数放左侧，比他小的数放右侧，等于它的数放中间，再将左侧和右侧进行递归调用，直到其长度为1
     */
    @Test
    public void test03() {
        int[] nums = {9, 3, 5, 1, 4, 7, 2, 6, 8, 0};
        fun3(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
    static Random random=new Random();
    public void fun3(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        //进行分组partition
        int less = l, more = r; //less:小的边界，more：大的边界
        int target = nums[l + random.nextInt(r - l + 1)];
        for (int i = l; i <= more; i++) {
            if (nums[i] < target) {
                replace(nums, i, less++);
            }
            if (nums[i] > target) {
                replace(nums, i--, more--);
            }
        }
        //对子集再进行分组
        fun3(nums, l, less - 1);
        fun3(nums, more + 1, r);
    }

    public void replace(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
